package com.duoduo.learn;

import java.util.*;

/**
 * @program: LearnAlgorithm
 * @description: 三数之和
 * @author: 拾光！
 * @create: 2021-05-28 20:37
 */
public class 三数之和 {
    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        int target = 0;
        List<List<Integer>> list = threeSum4(nums, target);
        System.out.println(list);
    }

    /**
     * 暴力解法
     *
     * @param nums
     * @param target
     * @return
     */
    public static List<List<Integer>> threeSum1(int[] nums, int target) {
        int n = nums.length;
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        list.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    }
                }
            }
        }
        return list;
    }

    /**
     * 暴力解法改进 结果去重
     *
     * @param nums
     * @param target
     * @return
     */
    public static List<List<Integer>> threeSum2(int[] nums, int target) {
        // int[] nums= {-1, 0, 1, 2, -1, -4};
        // int target=0;
        int length = nums.length;
        List<List<Integer>> result = new ArrayList<>();
        Map<Integer, List<Integer>> hashmap = new HashMap<>();
        for (int i = 0; i < length; i++) {
            int thatNum = target - nums[i];
            if (hashmap.containsKey(thatNum)) {
                List<Integer> tempList = new ArrayList<>(hashmap.get(thatNum));
                tempList.add(nums[i]);
                result.add(tempList);
                continue;
            }
            for (int j = 0; j < i; j++) {
                int newKey = nums[i] + nums[j];
                if (!hashmap.containsKey(newKey)) {
                    List<Integer> tempList = new ArrayList<>();
                    tempList.add(nums[j]);
                    tempList.add(nums[i]);
                    hashmap.put(newKey, tempList);
                }
            }
        }

        return result;
    }

    /**
     * 采用双指针算法，指针移动
     * @param nums
     * @param target
     * @return
     */
    public static List<List<Integer>> threeSum3(int[] nums, int target) {
        // int[] nums= {-1, 0, 1, 2, -1, -4};
        // int target=0;
        int n = nums.length;
        List<List<Integer>> result = new ArrayList<>();
        // 先对数组进行排序
        Arrays.sort(nums);
        for( int i = 0; i < n; i++ ){
            if( nums[i] > 0 ) {
                break;
            }
            if( i > 0 && nums[i] == nums[i-1] ) {
                continue;
            }
            // 定义左右指针（索引位置）
            int lp = i + 1;
            int rp = n - 1;
            // 只要左右不重叠，就继续移动指针
            while( lp < rp ){
                int sum = nums[i] + nums[lp] + nums[rp];
                if( sum == 0 ){
                    result.add(Arrays.asList(nums[i], nums[lp], nums[rp]));
                    lp ++;
                    rp --;
                    while( lp < rp && nums[lp] == nums[lp - 1] ) {
                        lp ++;
                    }
                    while( lp < rp && nums[rp] == nums[rp + 1] ) {
                        rp --;
                    }
                }
                else if( sum < 0 ) {
                    lp ++;
                } else {
                    rp --;
                }
            }
        }
        return result;
    }

    /**
     * 三数之和自己复写  采用双指针算法，指针移动
     * @param nums
     * @param target
     * @return
     */
    public static List<List<Integer>> threeSum4(int[] nums, int target) {
        int n = nums.length;
        List<List<Integer>> result=new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < n; i++) {
            //i<l<r   如果指针都大于0了，那么它们的三数之和不可能等于0
            if (nums[i]>0){
                break;
            }
            //i大于0，如果连续两个数相等，跳过次数，因为上一个数已经添加过了
            if (i>0 && nums[i]==nums[i-1]){
                continue;
            }
        //    定义左右指针
            int lp=i+1;
            int rp=n-1;
            // 只要左右不重叠，就继续移动指针
            while (lp<rp){
                int sum = nums[i] + nums[lp] + nums[rp];
                //如果结果等于0，保存到结果集中
                if (sum==target){
                    result.add(Arrays.asList(nums[i],nums[lp],nums[rp]));
                    lp++;
                    rp--;
                    //如果左指针和前一个数相等，说明重复，左指针继续往右跳
                    while (lp < rp && nums[lp] == nums[lp-1]){
                        lp++;
                    }
                    //如果右指针和后一个数相等，说明重复，右指针继续往左跳
                    while (lp<rp && nums[rp]==nums[lp - 1]){
                        lp--;
                    }
                }else if (sum<0){//如果和小于0，左指针右移
                    lp++;
                }else {//如果结果大于0，右指针左移
                    rp --;
                }


            }
        }
        return result;
    }
}
